| LeetCode

LeetCode-02-两数之和

1.题目描述

来源：力扣（LeetCode）

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
示例 1：


输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
示例 2：

输入：l1 = [0], l2 = [0]
输出：[0]
示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]
 

提示：

每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零

2.题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 总思路：初始化进位值为0，从个位数开始相加（即数组第一位），再加上进位值，相加之和大于9就设置进位为1，最后一位有进位也要加到最高位
        // 1.初始化工具变量
        // 1.1.虚拟一位指针，便于指向真实结果的头指针，返回结果
        ListNode vNode = new ListNode(0);
        // 1.2.初始化进位值
        int carry = 0;
        // 1.3.初始化遍历时的当前节点
        ListNode currentNode = vNode;

        // 2.从个位开始遍历及求和/进位值
        while(l1 != null || l2 != null) {
            // 2.1.获取俩加数的当前位的值，为空则为0，即高位为0便于加法计算
            int x = l1 != null ? l1.val : 0;
            int y = l2 != null ? l2.val : 0;

            // 2.2.求和：两个数的当前位的值以及当前进位值相加
            int sum = x + y + carry;
            // 2.3.求进位值
            carry = sum / 10;
            // 2.4.求进位后当前位的值
            sum = sum % 10;
            // 2.5.将当前值放入新节点
            currentNode.next = new ListNode(sum);

            // 2.6.将结果集的链表节点后移
            currentNode = currentNode.next;
            // 2.7.将两加数的链表后移
            if(l1 != null) {
                l1 = l1.next;
            }
            if(l2 != null) {
                l2 = l2.next;
            }
        }

        // 3.设置最高位：遍历完毕，进位值不为0则设置到最高位，即链表的最后
        if(carry != 0) {
            // 其实两个个位数相加最高位只会是1，这里的方式比较可扩展，比如三个数相加就可以用到
            currentNode.next = new ListNode(carry);
        }
        
        // 4.返回结果
        return vNode.next;
    }
}
ESC